import java.util.Arrays;

public class Sort {

    public void sortBubble(int[] a) {
        System.out.println("我是冒泡排序");
        bubble(a, a.length - 1);
    }

    public void sortInsertion(int[] a) {
        System.out.println("我是插入排序");
        insertion(a,1);
    }

    /**
     * 冒泡排序
     * @param a
     * @param j
     */
    private static void bubble(int[] a, int j) {
        System.out.println("================");
        System.out.println(Arrays.toString(a));
        if (j == 0) {
            return;
        }
        int x = 0; //有序和无序的分界线
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                x = i;
                System.out.println(Arrays.toString(a));
            }
        }
        System.out.println(Arrays.toString(a));
        bubble(a, x);
    }

    private static void insertion(int[] a,int low) {
        System.out.println("================");
        System.out.println(Arrays.toString(a));
        if (low == a.length) {
            return;
        }

        int t = a[low];
        int i = low - 1;

        while (i >= 0 && a[i] > t) {
           a[i + 1] = a[i];
           System.out.println(Arrays.toString(a) + " t=" + t + " i=" + i + " a[i]=" + a[i]);
           i--;
        }

        a[i + 1] = t;
        System.out.println(Arrays.toString(a));

        insertion(a, low + 1);
    }
}
